1016F - Road Projects - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;
const int c=300005;
int n, q, si[c];
vector<int> sz[c], s[c];
long long dist[c], pref[c], suf[c], tav, ert, tav2;
bool spec[c];

bool dfs(int a, int el) {
    if (a==n) {
        spec[a]=1;
        return true;
    }
    for (int i=0; i<si[a]; i++) {
        int x=sz[a][i], y=s[a][i];
        if (x!=el) {
            tav+=y;
            if (dfs(x, a)) {
                spec[a]=1;
                return true;
            }
            tav-=y;
        }
    }
    return false;
}

void dfs2(int a, int el) {
    pref[a]=max(pref[el], ert);;
    int kov=0, jo=0, lep=0;
    for (int i=0; i<si[a]; i++) {
        int x=sz[a][i], y=s[a][i];
        if (x==el) continue;
        if (spec[x]) {
            kov=x;
            lep=y;
            continue;
        }
        pref[a]=max(pref[a], ert+y);
        jo=1;
    }

    if (kov) {
        ert+=lep;
        dfs2(kov, a);
    }
}


void dfs3(int a, int el) {
    suf[a]=max(suf[el], ert);
    int kov=0, jo=0, lep=0;
    for (int i=0; i<si[a]; i++) {
        int x=sz[a][i], y=s[a][i];
        if (x==el) continue;
        if (spec[x]) {
            kov=x;
            lep=y;
            continue;
        }
        suf[a]=max(suf[a], ert+y);
        jo=1;
    }
    if (a==n) {
        if (jo) {
            tav2=max(tav2, suf[a]+pref[kov]);
        }
    } else {
        if (jo) {
            if (a!=1) tav2=max(tav2, suf[a]+pref[kov]);
            tav2=max(tav2, pref[a]+suf[el]);
        } else {
            if (a!=1) tav2=max(tav2, suf[el]+pref[kov]);
        }
    }

    if (kov) {
        ert+=lep;
        dfs3(kov, a);
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i=1; i<n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        sz[a].push_back(b), sz[b].push_back(a);
        s[a].push_back(c), s[b].push_back(c);
    }
    for (int i=1; i<=n; i++) {
        si[i]=sz[i].size();
    }
    dfs(1, 0);

    if (si[1]>=3 || si[n]>=3) {
        tav2=tav;
    }
    for (int i=1; i<=n; i++) {
        if (si[i]>=4) {
            tav2=tav;
        }
        if (!spec[i] && si[i]>=2) {
            tav2=tav;
        }
    }

    dfs2(1, 0);
    ert=0;
    dfs3(n, 0);


    while (q--) {
        long long x;
        cin >> x;
        //cout << "valasz............... ";
        cout << min(tav, tav2+x) << "\n";
    }
    return 0;
}